package queen;

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 * N Queen Problem.
 *
 * @author <a href="mailto:DL88250@gmail.com">Liang Ding</a>
 * @version 1.0.0.6, Mar 17, 2010
 */
final public class Queens {

    private static final int MAX_GENERATION_NUM = 10;
    private static final int MAX_POPULATION_NUM = 20000;
    private static List<Solution> population;
    private static float CROSSOVER_RATE = 0.7F;
    private static float MUTATION_RATE = 0.01F;
    private static Set<Solution> best;
    private static Set<Solution> better;
    private static final int EXPECTED_BEST_NUM = 5;

    static {
        population = new ArrayList<Solution>();
        best = new HashSet<Solution>();
        better = new HashSet<Solution>();
    }

    public static final void main(String[] args) {
        final int size = 16;

        init(size);
        compute();

        if (!better.isEmpty()) {
            printBetter();
        }

        if (!best.isEmpty()) {
            printBest();
        }

//        validate(new int[]{5, 2, 6, 3, 0, 7, 1, 4});
    }

    private static final void crossover() {
        final int crossoverNum = (int) (MAX_POPULATION_NUM * CROSSOVER_RATE);

        for (int i = 0; i < crossoverNum; i++) {
            final int solution1Idx = (int) (Math.random() * MAX_POPULATION_NUM);
            final int solution2Idx = (int) (Math.random() * MAX_POPULATION_NUM);
            final Solution solution1 = population.get(solution1Idx);
            final Solution solution2 = population.get(solution2Idx);
            final Solution child = solution1.crossover(solution2);

            population.add(child);
        }
    }

    private static void mutate() {
        final int mutationNum = (int) (MAX_POPULATION_NUM * MUTATION_RATE);

        for (int i = 0; i < mutationNum; i++) {
            final int idx = (int) (Math.random() * MAX_POPULATION_NUM);
            population.get(idx).mutate();
        }
    }

    private static final void printPopulation() {
        System.out.println("Population[size=" + population.size() + "]:");
        for (final Solution solution : population) {
            System.out.println(solution);
        }
    }

    private static final void printBetter() {
        System.out.println("Better[size=" + better.size() + "]:");
        final List<Solution> betterList = new ArrayList<Solution>(better);

        Collections.sort(betterList);

        for (final Solution solution : betterList) {
            System.out.println(solution);
        }
    }

    private static final void printBest() {
        System.out.println("Best[size=" + best.size() + "]:");
        for (final Solution solution : best) {
            System.out.println(solution);
        }
    }

    private static final void init(final int size) {
        for (int i = 0; i < MAX_POPULATION_NUM; i++) {
            population.add(new Solution(size));
        }
    }

    private static final void compute() {
        int generation = 0;

        while (generation < MAX_GENERATION_NUM
               && best.size() < EXPECTED_BEST_NUM) {
            crossover();

            Collections.<Solution>sort(population);
            refreshBest();

            eliminate();
            mutate();

//            printPopulation();
            generation++;
            System.out.println("G=" + generation);
        }
    }

    private static final void refreshBest() {
        for (int i = 0; i < population.size(); i++) {
            final Solution solution = population.get(i);
            final float fitness = solution.getFitness();
            if (0.99 < fitness && 1 != fitness) {
                better.add(solution.clone());
            }

            if (1 == fitness) {
                best.add(solution.clone());
            }
        }
    }

    private static final void eliminate() {
        final int eliminateNum = (int) (MAX_POPULATION_NUM * CROSSOVER_RATE);

        for (int i = 0; i < eliminateNum; i++) {
            population.remove(i);
        }
    }
}
